package leetcode.双指针法;

import java.util.Arrays;

/**
 * 最接近的三数之和
 *
 * 和第 15 题一样的思路，依然是来三个指针ijk
 * 当ijk指向的三数之和等于target的时候是最完美的答案，程序可以结束了
 * 若和大于 target 说明 k 偏大，k 需要 --，同时要去重
 * 若和小于  target 说明 j 偏小，j 需要 ++，同时要去重
 * 当 j 与 k 重合后，表示本次遍历结束，需要用新的 i 再来一遍遍历，同时要去重
 */
public class Test16最接近的三数之和 {

    public static int threeSumClosest(int[] nums, int target) {
        if (nums.length < 3) {
            return 0;
        }
        // 用来保存当前target与三数总和的差值的最小值
        int compare = Integer.MAX_VALUE;
        int sum = 0;
        Arrays.sort(nums);
        boolean goOn = true;
        for (int i = 0; i < nums.length; i++) {
            if (goOn == false) {
                break;
            }
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                // 先计算总和
                int s = nums[i] + nums[j] + nums[k];
                // 再计算差值
                int different = Math.abs(target - s);
                // 然后修改compare，保持compare的最小性，每一个最小的compare都有最接近target的sum
                if (different < compare) {
                    compare = different;
                    sum = s;
                }
                if (s == target) {
                    // 最好的情况
                    goOn = false;
                    break;
                } else if (s < target) {
                    while (j < k && nums[j] == nums[j + 1]) {
                        j++;
                    }
                    j++;
                } else {
                    while (j < k && nums[k] == nums[k - 1]) {
                        k--;
                    }
                    k--;
                }
            }
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,5,10,11};
        System.out.println(threeSumClosest(nums, 12));
    }
}
